//
// Created by liushuai on 2021/1/30.
//

#include "pathSum.h"
void pathSum(TreeNode* root, vector<int>& cache, vector<vector<int>>& paths,
             int value) {
  if (!root) return;
  cache.push_back(root->val);
  if (!root->left && !root->right && value - root->val == 0)
    paths.push_back(cache);

  pathSum(root->left, cache, paths, value - root->val);
  pathSum(root->right, cache, paths, value - root->val);
  cache.pop_back();  // 左右节点均不合适，此时节点应该被剔除
}
vector<vector<int>> pathSum(TreeNode* root, int value) {
  vector<int> cache;
  vector<vector<int>> result;
  pathSum(root, cache, result, value);
  return result;
}